package LinkedList;

public class Josephu {

  public static void main(String[] args) {
    CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();

//    添加小孩
    circleSingleLinkedList.addBoy(5);

//    遍历
    circleSingleLinkedList.showBoy();

//    出圈
    circleSingleLinkedList.countBoy(1,2,5);
  }

}

class CircleSingleLinkedList{
//  创建头结点
  private Boy first = new Boy(-1);

//  添加小孩
  public void addBoy(int nums){
    if (nums < 1){
      System.out.println("nums不正确");
      return;
    }
    Boy curBoy = null;
    for (int i = 1; i <= nums ; i++) {
//      创建小孩节点
      Boy boy = new Boy(i);
//      先让自己形成一个环
      if (i == 1){
        first = boy;
        first.setNext(first);
        curBoy = first;
      }else {
//        使得新节点指向第一个节点，并且指针右移
        curBoy.setNext(boy);
        boy.setNext(first);
        curBoy = boy;
      }
    }
  }
//  遍历小孩
  public void showBoy(){
    if (first == null){
      System.out.println("没有小孩");
    }
//    需要一个辅助节点来帮助遍历
    Boy curBoy = first;
    while (true){
      if (curBoy.getNext() == first){
        break;
      }
      System.out.println("小孩的编号为：" + curBoy.getNo());
      curBoy = curBoy.getNext();//指针右移
    }
  }
//  小孩出圈
  public void countBoy(int startNum,int countNum,int nums){
    if (first == null || startNum < 1 || startNum > nums){
      System.out.println("参数有误");
      return;
    }
//    辅助节点
    Boy helper = first;
//    定位helper和first指针，使得helper的下一个指向first
    while (true) {
//      表示此时在最后一个节点
      if (helper.getNext() == first) {
        break;
      }
      helper = helper.getNext();
    }

//      报数前先移动指针
    for (int i = 0; i < startNum - 1; i++) {
      first = first.getNext();
      helper = helper.getNext();
    }

    while (true) {
      if (helper == first){
        break;//此时只有一个节点
      }
//      移动指针
      for (int i = 0; i < countNum - 1; i++) {
        first = first.getNext();
        helper = helper.getNext();
      }
      System.out.println("此时出圈的小孩" + first.getNo());
      first = first.getNext();
      helper.setNext(first);
    }
    System.out.println("此时出圈的小孩" + helper.getNo());

  }
}

class Boy{
  private int no;
  private Boy next;

  public Boy(int no){
    this.no = no;
  }

  public int getNo() {
    return no;
  }

  public void setNo(int no) {
    this.no = no;
  }

  public Boy getNext() {
    return next;
  }

  public void setNext(Boy next) {
    this.next = next;
  }
}
